package com.example.hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 *  返回所有可能的结果。答案可以按 任意顺序 返回。
 *
 *  示例 1：
 * 输入：s = "()())()"
 * 输出：["(())()","()()()"]
 *
 *  示例 2：
 * 输入：s = "(a)())()"
 * 输出：["(a())()","(a)()()"]
 *
 *  示例 3：
 * 输入：s = ")("
 * 输出：[""]
 */
public class Leetcode301_RemoveInvalidParentheses {

    public static void main(String[] args) {

        String s = "()())()";
        System.out.println(new Solution().removeInvalidParentheses(s));
    }

    static class Solution {
        public List<String> removeInvalidParentheses3(String s) {
            return null;
        }

        public List<String> removeInvalidParentheses2(String s) {
            return null;
        }

        /**
         * 回溯法
         * 首先我们利用括号匹配的规则求出该字符串 s 中最少需要去掉的左括号的数目 lremove 和右括号的数目 rremove，
         * 然后我们尝试在原字符串 s 中去掉 lremove 个左括号和 rremove 个右括号，
         * 最后检测剩余的字符串是否合法匹配，
         *
         * @param s
         * @return
         */
        public List<String> removeInvalidParentheses1(String s) {
            // 因为只有一种括号，可以使用计数法计算需要删掉的左右括号数量
            int lRemove = 0, rRemove = 0;
            int len = s.length();
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) == '(') {
                    lRemove++;
                } else if (s.charAt(i) == ')') {
                    if (lRemove == 0) rRemove++;
                    else lRemove--;
                }
            }
            Set<String> res = new HashSet<>();
            backTrack1(s, 0, lRemove, rRemove, res);
//            backTrack2(s, 0, 0, 0, lRemove, rRemove, res);

            return new ArrayList(res);
        }

        /**
         * 不进行任何剪枝的回溯
         * @param s
         * @param startIndex
         * @param lRemove
         * @param rRemove
         * @param res
         */
        private void backTrack1(String s, int startIndex, int lRemove, int rRemove, Set<String> res) {
            if (lRemove == 0 && rRemove == 0 && isValid(s)) {
                res.add(s);
                return;
            }

            for (int i = startIndex; i < s.length(); i++) {
                if (lRemove > 0 && s.charAt(i) == '(') {
                    backTrack1(s.substring(0, i) + s.substring(i + 1), i, lRemove - 1, rRemove, res);
                }

                if (rRemove > 0 && s.charAt(i) == ')') {
                    backTrack1(s.substring(0, i) + s.substring(i + 1), i, lRemove, rRemove - 1, res);
                }
            }
        }

        // 有剪枝的回溯
        private void backTrack2(String s, int startIndex,int lCount, int rCount, int lRemove, int rRemove, Set<String> res) {
            if (lRemove == 0 && rRemove == 0 && isValid(s)) {
                res.add(s);
                return;
            }

            for (int i = startIndex; i < s.length(); i++) {
                char cur = s.charAt(i);
                if (i == startIndex || cur != s.charAt(i - 1)) { // 剪枝1:cur != s.charAt(i - 1)连续相同的括号只需要搜索一次
                    if (lRemove + rRemove > s.length() - i) { // 剪枝2:
                        return;
                    }
                    if (lRemove > 0 && cur == '(') {
                        backTrack2(s.substring(0, i) + s.substring(i + 1), i,
                                lCount, rCount, lRemove - 1, rRemove, res);
                    }

                    if (rRemove > 0 && cur == ')') {
                        backTrack2(s.substring(0, i) + s.substring(i + 1), i,
                                lCount, rCount, lRemove, rRemove - 1, res);
                    }
                }

                if (cur == '(') {
                    lCount++;
                } else if (cur == ')') {
                    rCount++;
                }
                if (rCount > lCount) {// 剪枝3:得到的序列中的右括号比左括号多，不需要再进行尝试后面的了
                    break;
                }
            }
        }

        private boolean isValid(String s) {
            int count = 0;
            int len = s.length();
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) == '(') ++count;
                else if (s.charAt(i) == ')'){
                    if (count == 0) return false;
                    else --count;
                }
            }
            return count == 0;
        }

        public List<String> removeInvalidParentheses(String s) {
            return removeInvalidParentheses1(s);
        }
    }
}
